#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int size; /* 当前堆元素个数 */
    int *data; /* 下标从1开始存储，0存放临时数据 */
    int max_size;  /* 最大元素个数 */
} Heap;


void show(Heap *heap)
{
    for (int i = 1; i <= heap->size; i++) {
        printf("%d ", heap->data[i]);
        if (((i + 1) & i) == 0) {
            printf("\b\n");
        }
    }
    printf("\n\n");
}

int up(Heap *heap, int pos)
{
    int child_index = pos;
    int parent_index = child_index / 2;
    while (parent_index >= 1) {
        if (heap->data[child_index] < heap->data[parent_index]) {
            heap->data[0] = heap->data[child_index];
            heap->data[child_index] = heap->data[parent_index];
            heap->data[parent_index] = heap->data[0];

            int tmp = parent_index;
            parent_index /= 2;
            child_index = tmp;
        } else {
            break;
        }
    }

    return 0;
}

int down(Heap *heap, int pos)
{
    int parent_index = pos;
    while (parent_index * 2 <= heap->size) {
        int left_index = 2 * parent_index;
        int right_index = 2 * parent_index + 1;

        /* 求左右的最小值 */
        int min_index = left_index;
        if (right_index <= heap->size && heap->data[right_index] < heap->data[left_index]) {
            min_index = right_index;
        }

        /* 比较最小值和父节点值，交换 */
        if (heap->data[min_index] < heap->data[parent_index]) {
            heap->data[0] = heap->data[min_index];
            heap->data[min_index] = heap->data[parent_index];
            heap->data[parent_index] = heap->data[0];
            parent_index = min_index;
        } else {
            break;
        }
    }

    return 0;
}

int init_heap(Heap *heap, int max, int *data, int len)
{
    if (len > max) {
        return 1;
    }

    heap->size = len;
    heap->max_size = max;
    heap->data = (int *)malloc((max + 1) * sizeof(int));

    heap->data[0] = 0;
    for (int i = 0; i < len; i++) {
        heap->data[i + 1] = data[i];
    }

    for (int i = heap->size / 2; i >= 1; i--) {
        int parent_index = i;
        down(heap, parent_index);
    }

    return 0;
}

int add(Heap *heap, int data)
{
    if (heap->size == heap->max_size) {
        return 1;
    }

    heap->size++;
    heap->data[heap->size] = data;

    int child_index = heap->size;
    up(heap, child_index);

    return 0;
}

/* 删除堆顶元素 */
int pop(Heap *heap)
{
    if (heap->size ==0) {
        return 1;
    }

    heap->data[1] = heap->data[heap->size];
    heap->size--;

    int parent_index = 1;
    down(heap, parent_index);

    return 0;
}

void destroy_heap(Heap *heap)
{
    heap->size = 0;
    heap->max_size = 0;
    free(heap->data);
}

int main(int argc, char const *argv[])
{
    int a[] = { 5, 1, 13, 3, 16, 7, 10, 14, 6, 9 };
    int len = sizeof(a) / sizeof(a[0]);

    Heap heap;
    init_heap(&heap, 1024, a, len);
    show(&heap);

    add(&heap, 0);
    show(&heap);

    add(&heap, -1);
    show(&heap);

    pop(&heap);
    show(&heap);

    destroy_heap(&heap);

    return 0;
}
